// 背包问题

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

/*
John
Bessie 拉的车最多能拉走 10 斤药材

总金额, 重量
[1, 2]
[4, 3]
[5, 6]
[6, 7]

前提：不能只拿一部分

1. 当 Bessie 不超重的情况下，最多带走多少钱的药材？ 10
2. 当钱数最多的时候，分别都拿了哪些药材？ 1，3
*/
vector<int> getIndices(
  const vector<vector<int>> &records, 
  const vector<vector<int>> &items);

int solve(const vector<vector<int>> &items, int capacity) {
  vector<int> values(capacity + 1, 0);
  vector<vector<int>> records(items.size() + 1, values);

  for (int i = 1; i < items.size() + 1; ++i) {
    for (int c = 1; c < capacity + 1; ++c) {
      int value = items[i - 1][0];
      int weight = items[i - 1][1];
      
      if (weight > c) {
        records[i][c] = records[i - 1][c];
      }
      else {
        records[i][c] = max(records[i - 1][c], value + records[i - 1][weight - c]);
      }
    }
  }

  auto indices = getIndices(records, items);

  for (int idx : indices) {
    cout << idx << " ";
  }
  cout << endl;

  return records.back().back();
}

vector<int> getIndices(
  const vector<vector<int>> &records, 
  const vector<vector<int>> &items) {
  vector<int> indices;

  int maxValue = records.back().back();
  int row = records.size() - 1;
  int col = records.front().size() - 1;

  while (row != 0) {
    if (records[row][col] != records[row - 1][col]) {
      // We get the item at current row
      indices.push_back(row);
      col -= items[row - 1][1]; // items does not have the zero row
    }

    --row;
  }

  return indices;
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<vector<int>> items {
    {1, 2},
    {4, 3},
    {5, 6},
    {6, 7}
  };

  cout << solve(items, 10) << endl;
  return 0;
}
